/*
https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/
 */
public class Solution214 {
    public String shortestPalindrome(String s) {
        int[] f=new int[s.length()];
        for (int i=1,j=0;i<s.length();i++){
            while (j>0 && s.charAt(i)!=s.charAt(j)){
                j=f[j-1];
            }
            if (s.charAt(i)==s.charAt(j)){
                j++;
            }
            f[i]=j;
        }
        int ans=0;
        for (int i=s.length()-1,j=0;i>=0;i--){
            while (j>0 && s.charAt(i)!=s.charAt(j)){
                j=f[j-1];
            }
            if (s.charAt(i)==s.charAt(j)){
                j++;
            }
            if (i==0){
                ans=j;
            }
        }
        return new StringBuilder(s.substring(ans)).reverse().toString().concat(s);
    }

    public static void main(String[] args) {
        System.out.println(new Solution214().shortestPalindrome("aacecaaa"));
    }
}
